import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

import java.util.Stack;
import java.util.stream.Stream;

/**
 * 接雨水
 * 题目：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * <p>
 * 示例 1：
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 * <p>
 * 示例 2：
 * 输入：height = [4,2,0,3,2,5]
 * 输出：9
 * <p>
 * 提示：
 * n == height.length
 * 0 <= n <= 3 * 104
 * 0 <= height[i] <= 105
 * <p>
 * 来源：力扣（LeetCode-42）
 * 链接：https://leetcode-cn.com/problems/trapping-rain-water
 *
 * @author godfrey
 * @since 2020-11-09
 */
@DisplayName("接雨水")
public class Trap extends BaseTest {

    static Stream<Arguments> testArguments() {
        return Stream.of(
                Arguments.arguments((Object) new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}),
                Arguments.arguments((Object) new int[]{4, 2, 0, 3, 2, 5})
        );
    }

    @DisplayName("按行求(会超时)-最大数是m，时间复杂度O(mn)，空间复杂度O(1)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void trap(int[] height) {
        int sum = 0, max = 0;
        //找出最大值
        for (int h : height) {
            if (h > max) {
                max = h;
            }
        }
        //标记是否更新
        boolean isUpdate = false;
        int tempSum = 0;
        for (int i = 1; i <= max; ++i) {
            isUpdate = false;
            tempSum = 0;
            for (int h : height) {
                if (isUpdate && h < i) {
                    ++tempSum;
                }
                if (h >= i) {
                    sum += tempSum;
                    tempSum = 0;
                    isUpdate = true;
                }
            }
        }
        System.out.println(sum);
    }

    @DisplayName("按列求-时间复杂度O(n^2)，空间复杂度O(n)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void trap2(int[] height) {
        int sum = 0;
        //最两端的列不用考虑，因为一定不会有水。所以下标从 1 到 length - 2
        for (int i = 1; i < height.length; ++i) {
            int maxLeft = 0;
            //找出左边最高
            for (int j = i - 1; j >= 0; --j) {
                if (height[j] > maxLeft) {
                    maxLeft = height[j];
                }
            }
            int maxRight = 0;
            //找出右边最高
            for (int j = i + 1; j < height.length; ++j) {
                if (height[j] > maxRight) {
                    maxRight = height[j];
                }
            }
            //找出两端较小的
            int min = Math.min(maxLeft, maxRight);
            //只有较小的一段大于当前列的高度才会有水，其他情况不会有水
            if (min > height[i]) {
                sum += min - height[i];
            }
        }
        System.out.println(sum);
    }

    @DisplayName("动态规划-时间复杂度O(n)，空间复杂度O(n)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void trap3(int[] height) {
        int sum = 0;
        int[] maxLeft = new int[height.length];
        int[] maxRight = new int[height.length];
        for (int i = 1; i < height.length; ++i) {
            //找出左边最大值
            maxLeft[i] = Math.max(maxLeft[i - 1], height[i - 1]);
        }
        for (int i = height.length - 2; i >= 0; --i) {
            //找出右边最大值
            maxRight[i] = Math.max(maxRight[i + 1], height[i + 1]);
        }
        for (int i = 0; i < height.length; ++i) {
            //找出两者较小的
            int min = Math.min(maxLeft[i], maxRight[i]);
            //较小的大于当前列，说明有水
            if (min > height[i]) {
                sum += min - height[i];
            }
        }
        System.out.println(sum);
    }

    @DisplayName("双指针-时间复杂度O(n)，空间复杂度O(1)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void trap4(int[] height) {
        int sum = 0, maxLeft = 0, maxRight = 0, left = 1, right = height.length - 2;
        for (int i = 1; i < height.length - 1; ++i) {
            //从左到右更
            if (height[left - 1] < height[right + 1]) {
                maxLeft = Math.max(maxLeft, height[left - 1]);
                if (maxLeft > height[left]) {
                    sum += maxLeft - height[left];
                }
                ++left;
                //从右到左更
            } else {
                maxRight = Math.max(maxRight, height[right + 1]);
                if (maxRight > height[right]) {
                    sum += maxRight - height[right];
                }
                --right;
            }
        }
        System.out.println(sum);
    }

    @DisplayName("栈-时间复杂度O(n)，栈空间")
    @ParameterizedTest
    @MethodSource("testArguments")
    void trap5(int[] height) {
        int sum = 0, current = 0;
        Stack<Integer> stack = new Stack<>();
        while (current < height.length) {
            //如果栈不空并且当前指向的高度大于栈顶高度就一直循环
            while (!stack.isEmpty() && height[current] > height[stack.peek()]) {
                //取出要出栈的元素
                int h = height[stack.peek()];
                //出栈
                stack.pop();
                //栈空就出去
                if (stack.isEmpty()) {
                    break;
                }
                //两堵墙之间的距离
                int distance = current - stack.peek() - 1;
                int min = Math.min(height[stack.peek()], height[current]);
                sum += distance * (min - h);
            }
            //当前指向的墙入栈
            stack.push(current);
            //指针后移
            ++current;
        }
        System.out.println(sum);
    }
}
